This paper presents a new motion planning algorithm, iDb-A*, that combines graph search and trajectory optimization iteratively. The search component uses short, precomputed motion primitives that can be stitched together with small discontinuities. This allows efficient exploration. The trajectory optimization step then repairs discontinuities, producing a smooth, feas...